首页 > 试题广场 >

数字字符串转化成IP地址

[编程题]数字字符串转化成IP地址

热度指数：67569 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 $0 \leq n \leq 12$

要求：空间复杂度 $O(n!)$ ,时间复杂度 $O(n!)$

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

示例1

输入

"25525522135"

输出

["255.255.22.135","255.255.221.35"]

示例2

输入

"1111"

输出

["1.1.1.1"]

示例3

输入

"000256"

输出

[]

算法知识视频讲解

Python 3

lvlvko

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # write code here
        l = len(s)
        ans = []

        def dfs(_s, _q):
            _l = len(_q)
            _sl = len(_s)
            if _l == 4 and not _sl:
                ans.append(".".join(_q))
                return
            if not _sl:
                return
            if _sl > (4 - _l) * 3:
                # 减枝
                return

            if _s[0] == "0":
                dfs(_s[1:], _q + [_s[:1]])
                # 前导0
                return
            for i in range(1, min(_sl, 3) + 1):
                if int(_s[:i]) > 255:
                    break
                dfs(_s[i:], _q + [_s[:i]])

        dfs(s, [])

        return ans

发表于 2023-09-12 16:36:25 回复(0)

Python 3

在研究求职打法的香菇

class Solution:
    def __init__(self):
        self.res = []
        self.tmp = []
    
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        n = len(s)
                # 判断字符串长度是否合理
        if n < 4&nbs***bsp;n > 12:
            return self.res
        self.dfs(s, 0, n)
        return self.res
        
    def dfs(self, s, start, n):
        # 分割了4个数字 and 下标走到末尾
        if len(self.tmp) == 4 and start == n:
            self.res.append(".".join(self.tmp))
            return
        # 索引越界&nbs***bsp;分割出了4个数字还没到末尾
        elif len(self.tmp) == 4&nbs***bsp;start >= n:
            return
        # 最长获取3个数字
        for i in range(start, start + 3):
            if i < n and 0<= int(s[start:i+1]) <= 255:
                # 遇前导 0 则 return
                if s[start] == "0" and i > start:
                    return
                self.tmp.append(s[start:i+1])
                self.dfs(s, i+1, n)
                self.tmp.pop()
            # 索引越界
            else:
                return

发表于 2022-08-19 23:31:16 回复(0)

Python 3

xuyjbug404

递归判断

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def recusion(self, res_str, cur_str, i):
        if i > 4:
            if res_str == "":
                self.vals.append(cur_str[1:])
            return
        
        min_l = len(res_str) - 3 * (4-i)
        max_l = len(res_str) - 1 * (4-i)

        if min_l > 3:
            return
        if max_l < 1:
            return
        min_l = max(1, min_l)
        max_l = min(3, max_l)
        if max_l < min_l:
            return
        for j in range(min_l, max_l+1):
            temp = res_str[:j]
            int_v = int(temp)
            if str(int_v) != temp:
                continue
            if int_v <= 255 and int_v >= 0:
                self.recusion(res_str[j:], cur_str + "." + temp, i+1)
        
        
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        self.vals = []
        self.recusion(s, '', 1)
        return self.vals

发表于 2022-08-12 13:46:32 回复(0)

Python 3

牛客801144222号

class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        # 对比用于跳出
        full_length = 12
        
        self.res = []
        tmp = []
        i = 0
        def recur(i, tmp):
            if len(tmp) > 4:
                return
            
            if i < len(s):
                tmp.append(s[i:i+1])
                i += 1
                if len(tmp) == 4 and i == len(s):
                    self.res.append(".".join(tmp))
                    i -= 1
                    tmp.pop()
                    return
                
                recur(i, tmp)
                i -= 1
                tmp.pop()
                
            if i < len(s) - 1 and s[i] != '0':
                tmp.append(s[i:i+2])
                i += 2
                if len(tmp) == 4 and i == len(s):
                    self.res.append(".".join(tmp))
                    i -= 2
                    tmp.pop()
                    return

                recur(i, tmp)
                
                i -= 2
                tmp.pop()
                
            if i < len(s) - 2 and int(s[i:i+3]) <= 255 and s[i] != '0':
                tmp.append(s[i:i+3])
                i += 3
                if len(tmp) == 4 and i == len(s):
                    self.res.append(".".join(tmp))
                    i -= 1
                    tmp.pop()
                    return
                
                recur(i, tmp)
                i -= 3
                tmp.pop()
        
        recur(i, tmp)
        
        return self.res

发表于 2022-06-10 11:02:57 回复(0)

Python 3

Vivimore

枚举所有分割点可能出现的位置，在根据分割点间数字的约束条件进行筛选，将合适的结果加入res

class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        res = []
        i = 1
        n = len(s)
        while i < 4 and i < n - 2:
            j = i + 1
            while j < i + 4 and j < n - 1:
                k = j + 1
                while k < j + 4 and k < n:
                    if n - k >= 4:
                        k += 1
                        continue
                    a = s[:i]
                    b = s[i:j]
                    c = s[j:k]
                    d = s[k:]
                    if int(a) > 255 or int(b) > 255 or int(c) > 255 or int(d) > 255:
                        k += 1
                        continue
                    if (len(a) > 1 and a[0] == '0') or (len(b) > 1 and b[0] == '0') or (len(c) > 1 and c[0] == '0') or (len(d) > 1 and d[0] == '0'):
                        k += 1
                        continue
                    temp = a + '.' + b + '.' + c + '.' + d
                    res.append(temp)
                    k += 1
                j += 1
            i += 1
        return res

发表于 2022-05-23 17:36:59 回复(0)

Python 3

JSFaner

class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        res = [] 
        def dfs(s,ans):
            if len(ans) == 4:
                if len(s) == 0:
                    res.append(".".join(ans))
                else:
                    return 
            l = min(3,len(s))
            for i in range(l):
                sub = s[:i+1]
                if 0<=int(sub)<=255 and str(int(sub)) == sub:
                    ans.append(sub)
                    dfs(s[i+1:],ans)
                    ans.pop() 
        dfs(s,[])
        return res

发表于 2022-02-19 21:56:36 回复(0)

Python 3

牛客114920445号

python3,回溯

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        def justify(ss):
            if ss == '0':
                return True
            if ss[0] == '0'&nbs***bsp;int(ss)>255:
                return False
            return True
        res = []
        def backtrack(st, pre):
            nonlocal res
            if not st and len(pre) == 4:
                res.append('.'.join(pre))
            elif st and len(pre) < 4:
                for i in range(1, 4):
                    if i<=len(st) and justify(st[:i]): #判断i防止下标越界造成的重复解
                        backtrack(st[i:], pre+[st[:i]])
        backtrack(s, [])
        return res

发表于 2022-02-19 18:16:43 回复(0)

Python 3

Acmen_沉梦昂志

class Solution:
	def restoreIpAddresses(self , s: str) -> List[str]:
		# write code here
		res = []
		def dfs(index,cur,cnt):
#			if indexlen(index)
			if index == len(s):
				if cnt == 4:
					res.append(cur[::])
				return
			if s[index] == '0':
				if cnt < 3:
					dfs(index + 1,cur + '0' + '.',cnt + 1)
				if cnt == 3:
					dfs(index + 1,cur + '0',cnt + 1)
			else:
				for i in range(index+1,len(s)+1):
	#				print(s[index : i])
					if 1 <= int(s[index : i]) <= 255:
						if cnt < 3:
							dfs(i,cur + s[index : i] + '.',cnt + 1)
						if cnt == 3:
							dfs(i,cur + s[index : i],cnt+1)
		dfs(0,'',0)
		return res

简单的回溯

发表于 2022-02-11 15:09:30 回复(0)

Python 3

Stephenling

class Solution:
def restoreIpAddresses(self , s ):
# write code here
def helper(tem, begin, cnt, res, size):
if cnt > 4:
return

if cnt == 4 and len(tem) == size+4:
res.append(tem[:-1])

for i in range(begin+1, begin + 4):
if i > size :
break
if s[begin:i] and int(s[begin:i]) > 255:
continue
if s[begin] == '0':
helper( tem + '0' + ".", i, cnt + 1, res, size)
else:
helper( tem + s[begin:i] + ".", i, cnt + 1, res, size)
return res
res = []
size = len(s)
helper('', 0, 0, res, size)

return res

发表于 2021-08-10 22:13:52 回复(0)